'''
统计一个数字在排序数组中出现的次数

解题思路： python中的count可以一行干掉
        但是考虑有序第一时间想到二分查找
        先找到第一个k的位置然后分别向左向右查找+1
'''
class Solution:
    def GetNumberOfK(self, data, k):
        if not data:
            return 0
        start = 0
        end = len(data) - 1
        while start <= end:
            mid = int((end + start)/2)
            if mid > k:
                end = mid-1
            elif mid < k:
                start = mid+1
            else:
                break
        if data[mid] != k:
            return 0
        pk = mid
        count = -1
        while pk < len(data) and data[pk] == k:
            count += 1
            pk += 1
        pk = mid
        while pk >= 0 and data[pk] == k:
            count += 1
            pk -= 1
        return count